package 力扣日常刷题.木22二月.第20天226;

import java.util.Arrays;

/**
 * @author 帅小伙
 * @date 2022/2/26
 * @description
 */
public class Demo164统计数组中好三元组数目 {

    private int n;
    //t 表示树状数组
    //树状数组用于存取，元素所对应的下标
    private final int[] t = new int[100001];

    public long goodTriplets(int[] nums1, int[] nums2) {
        n = nums1.length;
        // 用于记录nums2中各元素出现的位置
        int[] idxs = new int[100001], left = new int[n];
        for (int i = 0; i < n; i++)
            idxs[nums2[i]] = i;

        //left数组用于标记，nums1[i]之前有哪些数
        //从左到右，更新left数组
        for (int i = 0; i < n; i++) {
            int idx = idxs[nums1[i]];
            left[i] = sum(idx + 1);
            add(idx + 1);
        }
        Arrays.fill(t, 0);
        long ans = 0;
        //从右往左进行遍历
        for (int i = n - 1; i >= 0; i--) {
            int idx = idxs[nums1[i]];
            ans += (long) left[i] * (sum(n) - sum(idx + 1));
            add(idx + 1);
        }
        return ans;
    }

    private void add(int x) {
        //因为树状数组t中，储存的为下标，所以最大下标+1应该为n
        for (; x <= n; x += x & (-x)) t[x]++;
    }

    private int sum(int x) {
        int sum = 0;
        for (; x > 0; x -= x & (-x)) sum += t[x];
        return sum;
    }

}
